package bs;

import com.sun.xml.internal.txw2.output.IndentingXMLStreamWriter;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2023-01-06
 * Time: 22:24
 */
//局部最小值问题
public class BSAwesome {
    //得到局部最小值下标
    public static int getIndex(int[] arr){
        if(arr==null || arr.length==0){
            return -1;
        }
        //头部就是局部最小值
        if(arr.length==1 || arr[0]<arr[1]){
            return 0;
        }
        if(arr[arr.length-1]<arr[arr.length-2]){
            return arr.length-1;
        }
        int l=1;
        int r=arr.length-2;
        while (l<r){
            int mid=l+((r-l)>>1);
            if(arr[mid]>arr[mid-1]){
                r=mid-1;
            }else if(arr[mid]>arr[mid+1]){
                l=mid+1;
            }else {
                //arr[mid-1]>arr[mid] && arr[mid]<arr[mid+1]
                return mid;
            }
        }
        //l和r碰在一起
        return l;
    }
    //验证下标是不是局部最小
    public static boolean isRight(int[] arr,int index){
        if(arr.length<=1){
            return true;
        }
        if(index==0){
            return true;
        }
        if(index==arr.length-1){
            return arr[index]<arr[index-1];
        }
        return arr[index-1]>arr[index] && arr[index]<arr[index+1];
    }
    //随即数组
    // 生成相邻不相等的数组
    public static int[] generateRandomArray(int maxSize,int maxValue){
        int[] arr=new int[(int)(Math.random()*maxSize)+1]; //数组最小得有一个元素
        arr[0] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
        for(int i=1;i<arr.length;i++){
            do{
                arr[i]=(int)(Math.random() * maxValue) -(int) (Math.random()*maxValue);
            }while (arr[i]==arr[i-1]);
        }
        return arr;
    }
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 30;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            int ans = getIndex(arr);
            if (!isRight(arr, ans)) {
                System.out.println("出错了！");
                break;
            }
        }
        System.out.println("测试结束");
    }
}
